home *** CD-ROM | disk | FTP | other *** search
/ Atari Mega Archive 1 / Atari Mega Archive - Volume 1.iso / archiver / compress.arc / COMPRESS.C next >
C/C++ Source or Header  |  1987-08-17  |  41KB  |  1,494 lines
  1. /* 
  2.  * Compress - data compression program 
  3.  */
  4. #define    min(a,b)    ((a>b) ? b : a)
  5. #define ATARI    /* MWC for ATARI ST */
  6. /*
  7.  * machine variants which require cc -Dmachine:  pdp11, z8000, pcxt
  8.  */
  9.  
  10. /*
  11.  * Set USERMEM to the maximum amount of physical user memory available
  12.  * in bytes.  USERMEM is used to determine the maximum BITS that can be used
  13.  * for compression.
  14.  *
  15.  * SACREDMEM is the amount of physical memory saved for others; compress
  16.  * will hog the rest.
  17.  */
  18. #ifndef SACREDMEM
  19. #define SACREDMEM    0
  20. #endif
  21.  
  22. #ifndef USERMEM
  23. # define USERMEM     100000    /* default user memory */
  24. #endif
  25.  
  26. #ifdef interdata        /* (Perkin-Elmer) */
  27. #define SIGNED_COMPARE_SLOW    /* signed compare is slower than unsigned */
  28. #endif
  29.  
  30. #ifdef pdp11
  31. # define BITS     12    /* max bits/code for 16-bit machine */
  32. # define NO_UCHAR    /* also if "unsigned char" functions as signed char */
  33. # undef USERMEM 
  34. #endif /* pdp11 */    /* don't forget to compile with -i */
  35.  
  36. #ifdef z8000
  37. # define BITS     12
  38. # undef vax        /* weird preprocessor */
  39. # undef USERMEM 
  40. #endif /* z8000 */
  41.  
  42. #ifdef pcxt
  43. # define BITS   12
  44. # undef USERMEM
  45. #endif /* pcxt */
  46. #ifdef ATARI
  47. #define BITS 13
  48. #define SIGNED_COMPARE_SLOW
  49. #undef USERMEM
  50. #endif        /* MWC on ATARI 520 SHOULD WORK */
  51. #ifdef USERMEM
  52. # if USERMEM >= (433484+SACREDMEM)
  53. #  define PBITS    16
  54. # else
  55. #  if USERMEM >= (229600+SACREDMEM)
  56. #   define PBITS    15
  57. #  else
  58. #   if USERMEM >= (127536+SACREDMEM)
  59. #    define PBITS    14
  60. #   else
  61. #    if USERMEM >= (73464+SACREDMEM)
  62. #     define PBITS    13
  63. #    else
  64. #     define PBITS    12
  65. #    endif
  66. #   endif
  67. #  endif
  68. # endif
  69. # undef USERMEM
  70. #endif /* USERMEM */
  71.  
  72. #ifdef PBITS        /* Preferred BITS for this memory size */
  73. # ifndef BITS
  74. #  define BITS PBITS
  75. # endif
  76. #endif /* PBITS */
  77.  
  78. #if BITS == 16
  79. # define HSIZE    69001        /* 95% occupancy */
  80. #endif
  81. #if BITS == 15
  82. # define HSIZE    35023        /* 94% occupancy */
  83. #endif
  84. #if BITS == 14
  85. # define HSIZE    18013        /* 91% occupancy */
  86. #endif
  87. #if BITS == 13
  88. # define HSIZE    9001        /* 91% occupancy */
  89. #endif
  90. #if BITS <= 12
  91. # define HSIZE    5003        /* 80% occupancy */
  92. #endif
  93.  
  94. #ifdef M_XENIX            /* Stupid compiler can't handle arrays with */
  95. # if BITS == 16            /* more than 65535 bytes - so we fake it */
  96. #  define XENIX_16
  97. # else
  98. #  if BITS > 13            /* Code only handles BITS = 12, 13, or 16 */
  99. #   define BITS    13
  100. #  endif
  101. # endif
  102. #endif
  103.  
  104. /*
  105.  * a code_int must be able to hold 2**BITS values of type int, and also -1
  106.  */
  107. #if BITS > 15
  108. typedef long int    code_int;
  109. #else
  110. typedef int        code_int;
  111. #endif
  112.  
  113. #ifdef SIGNED_COMPARE_SLOW
  114. typedef unsigned long int count_int;
  115. typedef unsigned short int count_short;
  116. #else
  117. typedef long int      count_int;
  118. #endif
  119. #undef NO_UCHAR
  120. #ifdef NO_UCHAR
  121.  typedef char    char_type;
  122. #else
  123.  typedef    unsigned char    char_type;
  124. #endif /* UCHAR */
  125. char_type magic_header[] = { "\037\235" };    /* 1F 9D */
  126.  
  127. /* Defines for third byte of header */
  128. #define BIT_MASK    0x1f
  129. #define BLOCK_MASK    0x80
  130. /* Masks 0x40 and 0x20 are free.  I think 0x20 should mean that there is
  131.    a fourth header byte (for expansion).
  132. */
  133. #define INIT_BITS 9            /* initial number of bits/code */
  134.  
  135. /*
  136.  * compress.c - File compression ala IEEE Computer, June 1984.
  137.  *
  138.  * Authors:    Spencer W. Thomas    (decvax!harpo!utah-cs!utah-gr!thomas)
  139.  *        Jim McKie        (decvax!mcvax!jim)
  140.  *        Steve Davies        (decvax!vax135!petsd!peora!srd)
  141.  *        Ken Turkowski        (decvax!decwrl!turtlevax!ken)
  142.  *        James A. Woods        (decvax!ihnp4!ames!jaw)
  143.  *        Joe Orost        (decvax!vax135!petsd!joe)
  144.  *
  145.  * $Header: compress.c,v 4.0 85/07/30 12:50:00 joe Release $
  146.  * $Log:    compress.c,v $
  147.  * Revision 4.0  85/07/30  12:50:00  joe
  148.  * Removed ferror() calls in output routine on every output except first.
  149.  * Prepared for release to the world.
  150.  * 
  151.  * Revision 3.6  85/07/04  01:22:21  joe
  152.  * Remove much wasted storage by overlaying hash table with the tables
  153.  * used by decompress: tab_suffix[1<<BITS], stack[8000].  Updated USERMEM
  154.  * computations.  Fixed dump_tab() DEBUG routine.
  155.  *
  156.  * Revision 3.5  85/06/30  20:47:21  jaw
  157.  * Change hash function to use exclusive-or.  Rip out hash cache.  These
  158.  * speedups render the megamemory version defunct, for now.  Make decoder
  159.  * stack global.  Parts of the RCS trunks 2.7, 2.6, and 2.1 no longer apply.
  160.  *
  161.  * Revision 3.4  85/06/27  12:00:00  ken
  162.  * Get rid of all floating-point calculations by doing all compression ratio
  163.  * calculations in fixed point.
  164.  *
  165.  * Revision 3.3  85/06/24  21:53:24  joe
  166.  * Incorporate portability suggestion for M_XENIX.  Got rid of text on #else
  167.  * and #endif lines.  Cleaned up #ifdefs for vax and interdata.
  168.  *
  169.  * Revision 3.2  85/06/06  21:53:24  jaw
  170.  * Incorporate portability suggestions for Z8000, IBM PC/XT from mailing list.
  171.  * Default to "quiet" output (no compression statistics).
  172.  *
  173.  * Revision 3.1  85/05/12  18:56:13  jaw
  174.  * Integrate decompress() stack speedups (from early pointer mods by McKie).
  175.  * Repair multi-file USERMEM gaffe.  Unify 'force' flags to mimic semantics
  176.  * of SVR2 'pack'.  Streamline block-compress table clear logic.  Increase 
  177.  * output byte count by magic number size.
  178.  * 
  179.  * Revision 3.0   84/11/27  11:50:00  petsd!joe
  180.  * Set HSIZE depending on BITS.  Set BITS depending on USERMEM.  Unrolled
  181.  * loops in clear routines.  Added "-C" flag for 2.0 compatibility.  Used
  182.  * unsigned compares on Perkin-Elmer.  Fixed foreground check.
  183.  *
  184.  * Revision 2.7   84/11/16  19:35:39  ames!jaw
  185.  * Cache common hash codes based on input statistics; this improves
  186.  * performance for low-density raster images.  Pass on #ifdef bundle
  187.  * from Turkowski.
  188.  *
  189.  * Revision 2.6   84/11/05  19:18:21  ames!jaw
  190.  * Vary size of hash tables to reduce time for small files.
  191.  * Tune PDP-11 hash function.
  192.  *
  193.  * Revision 2.5   84/10/30  20:15:14  ames!jaw
  194.  * Junk chaining; replace with the simpler (and, on the VAX, faster)
  195.  * double hashing, discussed within.  Make block compression standard.
  196.  *
  197.  * Revision 2.4   84/10/16  11:11:11  ames!jaw
  198.  * Introduce adaptive reset for block compression, to boost the rate
  199.  * another several percent.  (See mailing list notes.)
  200.  *
  201.  * Revision 2.3   84/09/22  22:00:00  petsd!joe
  202.  * Implemented "-B" block compress.  Implemented REVERSE sorting of tab_next.
  203.  * Bug fix for last bits.  Changed fwrite to putchar loop everywhere.
  204.  *
  205.  * Revision 2.2   84/09/18  14:12:21  ames!jaw
  206.  * Fold in news changes, small machine typedef from thomas,
  207.  * #ifdef interdata from joe.
  208.  *
  209.  * Revision 2.1   84/09/10  12:34:56  ames!jaw
  210.  * Configured fast table lookup for 32-bit machines.
  211.  * This cuts user time in half for b <= FBITS, and is useful for news batching
  212.  * from VAX to PDP sites.  Also sped up decompress() [fwrite->putc] and
  213.  * added signal catcher [plus beef in writeerr()] to delete effluvia.
  214.  *
  215.  * Revision 2.0   84/08/28  22:00:00  petsd!joe
  216.  * Add check for foreground before prompting user.  Insert maxbits into
  217.  * compressed file.  Force file being uncompressed to end with ".Z".
  218.  * Added "-c" flag and "zcat".  Prepared for release.
  219.  *
  220.  * Revision 1.10  84/08/24  18:28:00  turtlevax!ken
  221.  * Will only compress regular files (no directories), added a magic number
  222.  * header (plus an undocumented -n flag to handle old files without headers),
  223.  * added -f flag to force overwriting of possibly existing destination file,
  224.  * otherwise the user is prompted for a response.  Will tack on a .Z to a
  225.  * filename if it doesn't have one when decompressing.  Will only replace
  226.  * file if it was compressed.
  227.  *
  228.  * Revision 1.9  84/08/16  17:28:00  turtlevax!ken
  229.  * Removed scanargs(), getopt(), added .Z extension and unlimited number of
  230.  * filenames to compress.  Flags may be clustered (-Ddvb12) or separated
  231.  * (-D -d -v -b 12), or combination thereof.  Modes and other status is
  232.  * copied with copystat().  -O bug for 4.2 seems to have disappeared with
  233.  * 1.8.
  234.  *
  235.  * Revision 1.8  84/08/09  23:15:00  joe
  236.  * Made it compatible with vax version, installed jim's fixes/enhancements
  237.  *
  238.  * Revision 1.6  84/08/01  22:08:00  joe
  239.  * Sped up algorithm significantly by sorting the compress chain.
  240.  *
  241.  * Revision 1.5  84/07/13  13:11:00  srd
  242.  * Added C versi